1060. Линии

В таблице из n строк и n столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.

Вход. В первой строке находится число n (2 ≤ n ≤ 40), в каждой из следующих n строк – по n символов. Символом точки обозначена свободная клетка, латинской заглавной O – шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X – конечное положение шарика.

Выход. В первой строке вывести Y, если движение возможно, или N, если нет. Если движение возможно, то далее следуют n строк по n символов – как и на вводе, но X, а также все точки на пути заменяются плюсами.

Пример входа	Пример выхода
5 ....X .OOOO ..... OOOO. @....	Y +++++ +OOOO +++++ OOOO+ @++++

РЕШЕНИЕ

графы – поиск в ширину - лабиринт

Анализ алгоритма

Запускаем поиск в ширину из одной из клеток, обозначенной символом @. Потом восстанавливаем кратчайший путь, если он существует.

Реализация алгоритма

Позицию на доске будем хранить парой координат (x, y), для этого объявим структуру CELL.

class Cell

{

public:

int x, y;

Cell(int x = 0, int y = 0) : x(x), y(y) {}

};

Объявим оператор сравнения ячеек “равно”.

int operator==(Cell a, Cell b)

{

return (a.x == b.x) && (a.y == b.y);

}

Состояние доски кодируем в массиве mas:

· mas[i][j] = 0 если в клетке находится символ @;

· mas[i][j] = -1 если клетка свободна, в ней изначально стоит точка;

· mas[i][j] = -2 если клетка занята шариком;

· mas[i][j] = -3 если в клетку будет поставлен плюс (+);

При поиске в ширину mas[i][j] будет хранить длину кратчайшего расстояния от клетки с символом @ до клетки (i, j).

Объявим рабочую очередь q для поиска в ширину.

#define MAX 50

int mas[MAX][MAX];

queue<Cell> q;

Функция CanGo возвращает 1, если можно пойти в точку с координатами (i, j).

int CanGo(int i, int j)

{

if ((i < 0) || (i >= n) || (j < 0) || (j >= n)) return 0;

if (mas[i][j] != -1) return 0;

return 1; // can go

}

Поиск в ширину из точки Start.

void bfs(Cell Start)

{

int dx[] = {1,-1,0,0};

int dy[] = {0,0,1,-1};

q.push(Start);

mas[Start.x][Start.y] = 0;

while (!q.empty())

{

Cell p = q.front(); q.pop();

if (p == finish) return; // destination reached

for (int k = 0; k < 4; k++)

{

int ii = p.x + dx[k]; // (x, y) -> (ii, jj)

int jj = p.y + dy[k];

if (CanGo(ii, jj))

{

q.push(Cell(ii, jj));

mas[ii][jj] = mas[p.x][p.y] + 1;

}

}

}

}

Основная часть программы. Читаем входные данные. В переменные start и finish заносим начальную и конечную позицию. Заполняем массив mas.

scanf("%d\n",&n);

for(i = 0; i < n; i++)

{

for(j = 0; j < n; j++)

{

scanf("%c",&ch);

mas[i][j] = -1;

if (ch == '@') // start position

start = Cell(i,j);

if (ch == 'X') // destination position

finish = Cell(i,j);

if (ch == 'O')

mas[i][j] = -2; // forbidden to move

}

scanf("\n");

}

Запускаем поиск в ширину.

bfs(start);

Если конечная точка не достижима, то выводим N.

if (mas[finish.x][finish.y] == -1)

{

printf("N\n");

return 0;

}

Иначе заполняем кратчайший путь плюсами.

printf("Y\n");

i = finish.x;

j = finish.y;

int cnt = mas[finish.x][finish.y];

for(k = 0; k < cnt; k++)

{

int ii = i, jj = j;

if ((i > 0) && (mas[i-1][j] == mas[i][j] - 1)) i--; else

if ((i < n - 1) && (mas[i+1][j] == mas[i][j] - 1)) i++; else

if ((j > 0) && (mas[i][j-1] == mas[i][j] - 1)) j--; else

if ((j < n) && (mas[i][j+1] == mas[i][j] - 1)) j++;

mas[ii][jj] = -3; // +

}

Выводим результирующую доску.

for(i = 0; i < n; i++)

{

for(j = 0; j < n; j++)

{

char c = '.';

if (mas[i][j] == -2) c = 'O';

if (mas[i][j] == 0) c = '@';

if (mas[i][j] == -3) c = '+';

printf("%c",c);

}

printf("\n");

}